package com.lft.hash_table;

import java.util.Scanner;

/**
 * 散列表
 */
public class HashTableDemo {
	public static void main(String[] args) {
		// 创建一个哈希表
		HashTab hashTab = new HashTab(4);
		// 写一个简单的菜单
		String key = "";
		Scanner scanner = new Scanner(System.in);
		while (true) {
			System.out.println("┌----------------┐");
			System.out.println("|---添加雇员(a)---|");
			System.out.println("|---显示雇员(l)---|");
			System.out.println("|---查找雇员(s)---|");
			System.out.println("|---修改雇员(u)---|");
			System.out.println("|---删除雇员(d)---|");
			System.out.println("|---退出系统(e)---|");
			System.out.println("└----------------┘");
			key = scanner.next();
			switch (key) {
				case "a":
					System.out.println("输入ID");
					int id = scanner.nextInt();
					System.out.println("输入NAME");
					String name = scanner.next();
					hashTab.add(new Emp(id, name));
					break;
				case "l":
					hashTab.list();
					break;
				case "s":
					System.out.println("输入要查找的ID");
					int searchId = scanner.nextInt();
					System.out.println(hashTab.get(searchId));
					break;
				case "u":
					System.out.println("输入要修改的雇员的ID");
					int updateId = scanner.nextInt();
					System.out.println("输入要修改的雇员的NAME");
					String updateName = scanner.next();
					hashTab.update(new Emp(updateId, updateName));
					break;
				case "d":
					System.out.println("输入要删除的雇员的ID");
					int deleteId = scanner.nextInt();
					hashTab.delete(deleteId);
					break;
				case "e":
					scanner.close();
					System.exit(0);
					break;
				default:
					break;
			}
		}
	}
}

/**
 * 创建 HashTab 管理多条链表
 */
class HashTab {
	private EmpLinkedList[] empLinkedListArray;
	
	public HashTab(int size) {
		// 初始化链表
		this.empLinkedListArray = new EmpLinkedList[size];
		// 大坑。记住一定要初始化链表。
		for (int i = 0; i < empLinkedListArray.length; i++) {
			empLinkedListArray[i] = new EmpLinkedList();
		}
	}
	
	/**
	 * 添加雇员
	 * @param emp 要添加的员工
	 */
	public void add(Emp emp) {
		// 根据员工的 ID，得到该员工应该添加到哪个链表。
		int empLinkedListNo = hashFun(emp.getId());
		// 将 emp 添加到对应的链表中。
		empLinkedListArray[empLinkedListNo].add(emp);
	}
	
	/**
	 * 计算 hash 值
	 * @param id 传入 id
	 * @return 取模后的索引
	 */
	private int hashFun(int id) {
		return id % empLinkedListArray.length;
	}
	
	/**
	 * 遍历所有的链表。遍历 HashTab
	 */
	public void list() {
		for (int i = 0; i < empLinkedListArray.length; i++) {
			empLinkedListArray[i].list(i);
		}
	}
	
	/**
	 * 通过 ID 获取雇员信息
	 * @param id 传入的雇员ID
	 * @return 雇员信息
	 */
	public Emp get(int id) {
		int empLinkedListNo = hashFun(id);
		return empLinkedListArray[empLinkedListNo].getEmp(id);
	}
	
	/**
	 * 通过 ID 修改雇员信息
	 * @param emp 传入要修改的雇员信息
	 */
	public void update(Emp emp) {
		int empLinkedListNo = hashFun(emp.getId());
		empLinkedListArray[empLinkedListNo].updateEmp(emp);
	}
	
	/**
	 * 通过 ID 删除雇员
	 * @param id
	 */
	public void delete(int id) {
		int empLinkedListNo = hashFun(id);
		empLinkedListArray[empLinkedListNo].deleteEmp(id);
	}
	
}

/**
 * 创建 EmpLinkedList 表示链表。
 */
class EmpLinkedList {
	// 头指针，指向第一个 Emp
	private Emp head;
	
	/**
	 * 添加雇员
	 * 说明：尾插法。每次添加都是添加到链表的最后。
	 * 1. 添加雇员时，id 自增，id 的分配总是从小到大。
	 * @param emp
	 */
	public void add(Emp emp) {
		// 如果添加第一个雇员
		if (head == null) {
			head = emp;
			return;
		}
		// 如果不是第一个雇员，遍历定位到最后一个。
		Emp tempEmp = head;
		while (tempEmp.getNext() != null) {
			tempEmp = tempEmp.getNext();
		}
		// 遍历完找到最后一个，将要添加的加入到链表。
		tempEmp.setNext(emp);
	}
	
	/**
	 * 遍历链表
	 */
	public void list(int empLinkedListNo) {
		if (head == null) {
			System.out.println("第 " + empLinkedListNo + " 条链表为空！");
			return;
		}
		Emp tempEmp = head;
		while (true) {
			
			System.out.println("第 " + empLinkedListNo + " 号链表中，ID: " + tempEmp.getId() + " , NAME: " + tempEmp.getName());
			if (tempEmp.getNext() == null) {
				break;
			}
			tempEmp = tempEmp.getNext();
		}
	}
	
	/**
	 * 根据 ID 查找雇员
	 * @param id 雇员ID
	 * @return 没有找到就返回null
	 */
	public Emp getEmp(int id) {
		if (head == null) {
			System.out.println("链表为空");
			return null;
		}
		Emp tempEmp = head;
		while (true) {
			if (tempEmp.getId() == id) {
				break;
			}
			if (tempEmp.getNext() == null) {
				tempEmp = null;
				break;
			}
			tempEmp = tempEmp.getNext();
		}
		return tempEmp;
	}
	
	/**
	 * 根据 ID 修改雇员
	 * @param emp 传入要修改的雇员信息
	 */
	public void updateEmp(Emp emp) {
		if (head == null) {
			System.out.println("链表为空");
			return;
		}
		Emp first = new Emp(Integer.MIN_VALUE, "");
		first.setNext(head);
		Emp tempEmp = first;
		while (true) {
			if (tempEmp.getNext().getId() == emp.getId()) {
				emp.setNext(tempEmp.getNext().getNext());
				tempEmp.setNext(emp);
				break;
			}
			if (tempEmp.getNext() == null) {
				break;
			}
			tempEmp = tempEmp.getNext();
		}
		head = first.getNext();
	}
	
	/**
	 * 根据 ID 删除雇员
	 * @param emp 传入要修改的雇员信息
	 */
	public void deleteEmp(int id) {
		if (head == null) {
			System.out.println("链表为空");
			return;
		}
		Emp first = new Emp(Integer.MIN_VALUE, "");
		first.setNext(head);
		Emp tempEmp = first;
		while (true) {
			if (tempEmp.getNext().getId() == id) {
				tempEmp.setNext(tempEmp.getNext().getNext());
				break;
			}
			if (tempEmp.getNext() == null) {
				break;
			}
			tempEmp = tempEmp.getNext();
		}
		head = first.getNext();
	}
}

/**
 * 雇员
 */
class Emp {
	private int id;
	private String name;
	private Emp next;
	
	public Emp(int id, String name) {
		this.id = id;
		this.name = name;
	}
	
	public int getId() {
		return id;
	}
	
	public void setId(int id) {
		this.id = id;
	}
	
	public String getName() {
		return name;
	}
	
	public void setName(String name) {
		this.name = name;
	}
	
	public Emp getNext() {
		return next;
	}
	
	public void setNext(Emp next) {
		this.next = next;
	}
	
	@Override
	public String toString() {
		return "Emp{" +
				"id=" + id +
				", name='" + name + '\'' +
				'}';
	}
}